#include <iostream>
#include "LinkList.h"

using namespace std;

int main0() {
    std::cout << "Hello, World!" << std::endl;
    LinkedNode* head = createLinkList();
    printLinkList(head);

    LinkedNode* head2 =  removeElements2(head, 1);
    printLinkList(head2);

    return 0;
}


LinkedNode* createLinkList(){
    LinkedNode * head = new LinkedNode(0);//堆区开辟内存
    //备份头结点，不然return时找不到
    LinkedNode * cur = head;

    int data[5] = {1,2,3,4,5};

    for (int i = 0; i < sizeof(data)/sizeof(int); ++i) {
        LinkedNode * node  = new LinkedNode(data[i]);
        cur->next = node;//cur->next 是指向堆区一块内存
        cur = cur->next;//cur指针在栈区，可以随便写入，指向当前指针的位置
    }

    return head;
}

void printLinkList(LinkedNode * head){
    LinkedNode * cur = head;
    while (cur!= nullptr){
        cout << cur->val << "-> ";
        cur = cur->next;
    }
    cout << "NULL "<<endl;
}

//删除指定节点 方法一 : 直接使用原来的链表来进行移除节点操作
LinkedNode* removeElements(LinkedNode* head, int val){

    //head 指针在栈区存储，作为指针进行移动，实际存储内容位于堆区保持不变，
    //通过给指针赋值，将指针指向的内存块修改，以此访问不同的内容

    //头结点特殊处理
    while (head!= nullptr && head->val == val){
        LinkedNode * temp = head;//临时存放地址
        head = head->next;
        delete temp;//将原来头结点释放
    }

    LinkedNode * cur = head;//新的头结点

    while (cur!= nullptr && cur->next!= nullptr){
        if(cur->next->val == val){
            LinkedNode * temp = cur->next;
            cur->next = temp->next;//如果删除节点则不进行移动，需要再次执行判断下一个节点是否还是目标节点
            delete temp;
        } else{
            cur = cur->next;//将当前节点移动
        }

    }

    return head;
}

//删除指定节点 方法二 : 设置一个虚拟头结点在进行移除节点操作
LinkedNode* removeElements2(LinkedNode* head, int val){
    LinkedNode * pListNode = new LinkedNode (0);
    pListNode->next = head;

    LinkedNode * cur = pListNode;//新的头结点

    while (cur->next!= nullptr){
        //LinkedNode * temp = cur->next; //!!! 错误 heap-use-after-free on address
        if(cur->next->val == val){
            LinkedNode * temp = cur->next;
            cur->next = temp->next;
            delete temp;
        } else{
            cur = cur->next;//将当前节点移动
        }
        //delete temp;
    }
    head= pListNode->next;
    delete pListNode;
    return head;
}

LinkedNode* removeElements3(LinkedNode* head, int val) {
    if(head==NULL){
        return head;
    }

    head->next = removeElements3(head->next,val);
    return head->val == val ? head->next : head;
}

